package algorithm.DivideConquer;

/**
 * 使用分治的思想，借助随机快速排序找到第k个元素的位置
 * 这样能把算法的时间复杂度降低为O(n)
 * 问题可以等价为寻找排序后的数组第k-1位元素，考虑改写快速排序
 * 这个问题有点类似于峰值问题
 * 这个问题用填函数的方式
 */
public class RandomSelect {

    public static int findKthLargest(int[] nums,int k){
        return randomSelect(nums,nums.length-k);
    }

    /**
     * 假设nums数组已经排好序了,这是对快速排序的改写
     * @param nums
     * @param i
     * @return
     */
    public static int randomSelect(int[] nums,int i){
        int ans=0;
        for(int l=0,r=nums.length-1;l<=r;){
            hollandFlagPartition(nums,l,r,nums[l+(int)(Math.random()*(r-l+1))]);
            if(i<start){
                r=end-1;
            }else if(i>end){
                l=end+1;
            }else{
                ans=nums[i];
                break;
            }
        }
        return ans;
    }

    /**
     * 荷兰国旗版本的分区方法操作的是下面这两个全局静态变量
     * start end表示与x相等区域的边界，都是闭的
     */
    public static int start;
    public static int end;

    /**
     * 荷兰国旗版本的分区方法
     * 将数组分为小于x，等于x，大于x的三个区域，对应有三个判断逻辑
     * @param l
     * @param r
     * @param x
     */
    public static void hollandFlagPartition(int[] nums,int l,int r,int x){

        start=l;
        end=r;
        //i是一个哨兵，只负责遍历元素
        int i=l;

        while(i<=end){
            if(nums[i]==x){
                i++;
            }else if(nums[i]<x){
                swap(nums,start++,i++);
            }else{
                swap(nums,i,end--);
            }
        }
    }

    public static void swap(int[] nums,int a,int b){
        int temp=nums[a];
        nums[a]=nums[b];
        nums[b]=temp;
    }

}
